class MyLinkedList {
    head;
    last;
    size=0;

    /**
     * 链表插入元素
     * @param index  插入位置
     * @param data  插入元素
     */
    insert(index, data) {
        if (index < 0 || index > this.size) {
            throw new Error("超出链表节点范围！");
        }
        const insertedNode = new Node(data);
        if (this.size === 0) {
            //空链表
            this.head = insertedNode;
            this.last = insertedNode;
        } else if (index === 0) {
            //插入头部
            insertedNode.next = this.head;
            this.head = insertedNode;
        } else if (this.size === index) {
            //插入尾部
            this.last.next = insertedNode;
            this.last = insertedNode;
        } else {
            //插入中间
            const prevNode = this.get(index - 1);
            insertedNode.next = prevNode.next;
            prevNode.next = insertedNode;
        }
        this.size++;
    }

    /**
     * 链表删除元素
     * @param index  删除的位置
     */
    remove(index) {
        if (index < 0 || index >= this.size) {
            throw new Error("超出链表节点范围！");
        }
        let removedNode = null;
        if (index === 0) {
            //删除头节点
            removedNode = this.head;
            this.head = this.head.next;
        } else if (index === this.size - 1) {
            //删除尾节点
            const prevNode = this.get(index - 1);
            removedNode = prevNode.next;
            prevNode.next = null;
            this.last = prevNode;
        } else {
            //删除中间节点
            const prevNode = this.get(index - 1);
            const nextNode = prevNode.next.next;
            removedNode = prevNode.next;
            prevNode.next = nextNode;
        }
        this.size--;
        return removedNode;
    }

    /**
     * 链表查找元素
     * @param index  查找的位置
     */
    get(index) {
        if (index < 0 || index >= this.size) {
            throw new Error("超出链表节点范围！");
        }
        let temp = this.head;
        for(let i = 0; i < index; i++) {
            temp = temp.next;
        }
        return temp;
    }

    /**
     * 输出链表
     */
    output(){
        let temp = this.head;
        while (temp!=null) {
            console.log(temp.data);
            temp = temp.next;
        }
    }
}

/**
 * 链表节点
 */
class Node {
    data;
    next;

    constructor(data) {
        this.data = data;
    }
}

function run() {
    const myLinkedList = new MyLinkedList();
    myLinkedList.insert(0,3);
    myLinkedList.insert(0,4);
    myLinkedList.insert(2,9);
    myLinkedList.insert(3,5);
    myLinkedList.insert(1,6);
    myLinkedList.remove(0);
    myLinkedList.output();
}

run();